package leetcode003;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * https://leetcode.cn/problems/longest-substring-without-repeating-characters/
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。
 */
public class Study003 {

    /**
     * 嵌套循环法
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            set.add(c);
            for (int j = i + 1; j < s.length(); j++) {
                if (!set.contains(s.charAt(j))) {
                    set.add(s.charAt(j));
                } else {
                    break;
                }
             }
            maxLength = Math.max(set.size(),maxLength);
            set.clear();
        }
        return maxLength;
    }

    /**
     * 滑动窗口法
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring2(String s) {
        int maxLength = 0;
        int startIndex = 0;
        Map<Character,Integer> map = new HashMap<>();
        for (int i = 1; i <= s.length(); i++) {
            char c = s.charAt(i - 1);
            Integer index = map.get(c);
            if (index != null && startIndex <= index) {
                startIndex = index;
            }
            int length = i - startIndex;
            maxLength = Math.max(maxLength,length);
            map.put(c, i);
        }
        return maxLength;
    }
}
